#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <cctype>
#include <limits>
#include <functional>
#include <algorithm>
using namespace std;

//=================================== Part1：数据结构模块 
//初始化结点
struct PhoneRecord {
    string phoneNumber; //电话号码
    string userName;    //用户姓名
    string address;     //地址

    PhoneRecord(string phone = "", string name = "", string addr = "")//初始化PhoneRecord的类   允许在创建对象不提供某些参数
        : phoneNumber(phone), userName(name), address(addr) {
    }
};
//初始化类
struct HashNode {
    PhoneRecord record;
    HashNode* next;
    //指向 HashNode 的指针，用于链接链表中的下一个节点
    HashNode(const PhoneRecord& rec) : record(rec), next(nullptr) {}
};
//record(rec)：将传入的 rec 参数赋值给 record 变量。
//next(nullptr)：将 next 指针初始化为 nullptr，表示当前节点没有指向下一个节点。

//=================================== Part2 散列表实现 
class HashTable {
private:
    vector<HashNode*> table;
    int tableSize;//选取质数101，将最后计算的结果限制到1至100之间，并且质数减少哈希冲突
    //哈希表的大小为100
    // 散列函数（乘法散列法）
    int hashFunction(const string& key) const {
        unsigned long hash = 0;
        const int stand = 31;     // 选择质数 31 作为乘法因子,选取质数来减少哈希冲突的概率

        for (char c : key) //循环依次取出 key 中的每一个字符，并将其赋值给 c
        {
            hash = (hash * stand) + static_cast<unsigned char>(c);//对C进行hash计算
        }
        return hash % tableSize;
    }

public:
    // 构造函数
    HashTable(int size = 101) : tableSize(size)
    {
        table.resize(tableSize, nullptr);
    }
    //将 table 的大小调整为 tableSize，并且将每个元素初始化为 nullptr。
    //桶初始时为空

    // 析构函数在程序结束时释放资源，清空散列表
    ~HashTable() {
        clear();
    }

    void clear() {
        for (int i = 0; i < tableSize; i++) {
            HashNode* current = table[i]; //遍历 table 中的每一个桶
            while (current != nullptr) {  //桶为不为空时执行while循环
                HashNode* next = current->next;
                delete current;
                current = next;
            }
            table[i] = nullptr;
        }
    }


    // 插入用户信息
    void insert(const PhoneRecord& record, const string& key) {
        int index = hashFunction(key);                      //哈希函数求存储位置
        HashNode* newNode = new HashNode(record);           //创建一个新的 HashNode 节点，并将 record 存储在其中。

        // 链地址法解决冲突（头插法）               //头插入桶中
        if (table[index] == nullptr) {
            table[index] = newNode;
        }
        else {
            newNode->next = table[index];
            table[index] = newNode;
        }
    }

    // 查找用户信息
    PhoneRecord* search(const string& key) {
        int index = hashFunction(key);          //计算散列值
        HashNode* node = table[index];          //寻找存储节点

        while (node != nullptr) {
            if (key == node->record.phoneNumber || key == node->record.userName) {
                return &(node->record);
            }
            node = node->next;   //没有查找到继续寻找
        }
        return nullptr;         //或者返回异常
    }

    // 检查关键字是否存在
    bool contains(const string& key) {
        return search(key) != nullptr;
    }

    //修改函数
    bool remove(const string& key) {
        int index = hashFunction(key);
        HashNode* current = table[index];
        HashNode* prev = nullptr;

        while (current != nullptr) {
            if (key == current->record.phoneNumber || key == current->record.userName) {
                if (prev == nullptr) {
                    table[index] = current->next;
                }
                else {
                    prev->next = current->next;
                }
                delete current;
                return true;
            }
            prev = current;
            current = current->next;
        }
        return false;
    }

    // 打印散列表统计信息
    void printStats() const {
        int collisions = 0;
        int maxChainLength = 0;
        int totalRecords = 0;

        cout << "\n===== 散列表统计信息 =====" << endl;
        cout << "表大小: " << tableSize << endl;

        for (int i = 0; i < tableSize; i++) {
            int chainLength = 0;
            HashNode* current = table[i];

            while (current != nullptr) {
                chainLength++;
                current = current->next;
            }

            if (chainLength > 0) {
                totalRecords += chainLength;
                if (chainLength > 1) collisions++;
                if (chainLength > maxChainLength) maxChainLength = chainLength;
            }
        }

        cout << "总记录数: " << totalRecords << endl;
        cout << "冲突桶数: " << collisions << endl;
        cout << "最大链长: " << maxChainLength << endl;
        cout << "冲突率: " << fixed << setprecision(2)
            << (collisions * 100.0 / tableSize) << "%" << endl;
        cout << "负载因子: " << fixed << setprecision(2)
            << (totalRecords * 1.0 / tableSize) << endl;
        cout << "============================" << endl;
    }
};

// =================================== Part3 输入验证模块 cctype
bool CheckPhoneNum(const string& phone) {
    if (phone.length() != 11) return false;
    for (char c : phone) {
        if (!isdigit(c)) return false;  //isdigit检查字符是否为数字
    }
    return true;
}

bool CheckUserName(const string& name) {
    if (name.empty()) return false;
    for (char c : name) {
        if (!isalpha(c) && !isspace(c)) return false;
    }
    return true;
}
//limits清除输入缓冲区
void clearInputBuffer() {
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n'); //当遇到换行符时停止忽略
}

// ==================================== Part4 用户信息输出函数 
void printHeader(const string& title) {                        //参数为title
    cout << "\n\033[1;32m" << string(60, '=') << "\033[0m" << endl;
    cout << "\033[3;32m" << setw(35) << title << "\033[0m" << endl;
    cout << "\033[1;32m" << string(60, '*') << "\033[0m" << endl;
}

void printRecord(const PhoneRecord& record) {               //姓名15以及电话20
    cout << left << setw(15) << record.phoneNumber
        << setw(20) << record.userName
        << record.address << endl;
}

void printRecordHeader() {
    cout << "\033[1;32m" << string(60, '-') << "\033[0m" << endl;  //电话号码、用户名、地址
    cout << "\033[1;32m" << left << setw(15) << "电话号码"
        << setw(20) << "用户名" << "地址\033[0m" << endl;
    cout << "\033[1;32m" << string(60, '-') << "\033[0m" << endl;
}

/*
\033[1; 36m：设置文本颜色
\033[是转义序列的开始。
1 表示启用粗体
36 表示设置前景色的色号
\033[0m：重置所有文本属性到默认值。
*/



// ==================================== Part4模糊查询功能
// 字符串转换为小写
string toLowerString(const string& str) {
    string lowerStr = str;
    transform(lowerStr.begin(), lowerStr.end(), lowerStr.begin(),
        [](unsigned char c) { return tolower(c); });
    return lowerStr;
}

// 模糊匹配函数
bool fuzzyMatch(const string& source, const string& pattern) {
    string sourceLower = toLowerString(source);
    string patternLower = toLowerString(pattern);

    // 空模式匹配所有
    if (patternLower.empty()) return true;

    // 子串匹配
    return sourceLower.find(patternLower) != string::npos;
}

// 执行模糊查询
void fuzzySearch(const vector<PhoneRecord>& records, const string& keyword) {
    printHeader("模糊查询结果: " + keyword);

    vector<PhoneRecord> results;
    for (const auto& rec : records) {
        if (fuzzyMatch(rec.phoneNumber, keyword) ||
            fuzzyMatch(rec.userName, keyword) ||
            fuzzyMatch(rec.address, keyword)) {
            results.push_back(rec);
        }
    }

    if (results.empty()) {
        cout << "\n\033[1;31m 未找到匹配记录！\033[0m" << endl;
        return;
    }

    cout << "找到 " << results.size() << " 条匹配记录\n";
    printRecordHeader();

    for (const auto& rec : results) {
        printRecord(rec);
    }
    cout << string(60, '-') << endl;
}

//============================================ Part5记录编辑功能

void editRecord(HashTable& phoneHash, HashTable& nameHash,
    vector<PhoneRecord>& allRecords) {
    string oldPhone;
    printHeader("编辑记录");
    cout << "请输入要编辑的电话号码: ";
    getline(cin, oldPhone);

    // 验证电话号码格式
    if (!CheckPhoneNum(oldPhone)) {
        cout << "\033[1;31m无效的电话号码格式！\033[0m" << endl;
        return;
    }

    // 在向量中查找记录（避免使用散列表指针）
    auto it = find_if(allRecords.begin(), allRecords.end(),
        [&](const PhoneRecord& rec) { return rec.phoneNumber == oldPhone; });

    if (it == allRecords.end()) {
        cout << "\033[1;31m记录不存在！\033[0m" << endl;
        return;
    }

    // 保存旧记录
    PhoneRecord oldRecord = *it;
    // 创建更新后的记录副本
    PhoneRecord newRecord = *it;

    // 显示当前记录
    printHeader("当前记录信息");
    printRecordHeader();
    printRecord(oldRecord);
    cout << string(60, '-') << endl;

    // 编辑电话号码
    while (true) {
        cout << "\n新电话号码 (留空保持不变，当前: " << oldRecord.phoneNumber << "): ";
        string newPhone;
        getline(cin, newPhone);

        if (newPhone.empty()) {
            // 用户选择不修改电话号码
            break;
        }

        if (!CheckPhoneNum(newPhone)) {
            cout << "\033[1;31m格式错误：必须为11位数字！\033[0m" << endl;
            continue;
        }

        // 检查新电话号码是否已被使用（排除自身）
        if (newPhone != oldRecord.phoneNumber && phoneHash.contains(newPhone)) {
            cout << "\033[1;31m该电话号码已被使用！\033[0m" << endl;
            continue;
        }

        newRecord.phoneNumber = newPhone;
        break;
    }

    // 编辑用户名
    while (true) {
        cout << "新用户名 (留空保持不变，当前: " << oldRecord.userName << "): ";
        string newName;
        getline(cin, newName);

        if (newName.empty()) {
            // 用户选择不修改用户名
            break;
        }

        if (!CheckUserName(newName)) {
            cout << "\033[1;31m格式错误：仅允许字母和空格！\033[0m" << endl;
            continue;
        }

        // 检查新用户名是否已被使用（排除自身）
        if (newName != oldRecord.userName && nameHash.contains(newName)) {
            cout << "\033[1;31m该用户名已被使用！\033[0m" << endl;
            continue;
        }

        newRecord.userName = newName;
        break;
    }

    // 编辑地址
    cout << "新地址 (留空保持不变，当前: " << oldRecord.address << "): ";
    string newAddr;
    getline(cin, newAddr);
    if (!newAddr.empty()) {
        newRecord.address = newAddr;
    }

    // 确认编辑
    cout << "\n请确认修改 (y/n): ";
    char confirm;
    cin >> confirm;
    clearInputBuffer();

    if (tolower(confirm) != 'y') {
        cout << "\033[1;33m编辑已取消\033[0m" << endl;
        return;
    }

    // 更新数据结构
    // 1. 从散列表中删除旧记录
    phoneHash.remove(oldRecord.phoneNumber);
    nameHash.remove(oldRecord.userName);

    // 2. 更新向量中的记录
    *it = newRecord;

    // 3. 向散列表添加更新后的记录
    phoneHash.insert(newRecord, newRecord.phoneNumber);
    nameHash.insert(newRecord, newRecord.userName);

    cout << "\n\033[1;32m✓ 记录更新成功！\033[0m" << endl;

    // 显示更新后的记录
    printHeader("更新后的记录");
    printRecordHeader();
    printRecord(newRecord);
    cout << string(60, '-') << endl;
}


// ====================== 主程序模块 ======================
int main() {
    HashTable phoneHash;
    HashTable nameHash;
    vector<PhoneRecord> allRecords;

    // 预置记录
    vector<PhoneRecord> initialRecords = {
        {"13007075864", "Zhang San", "Beijing Haidian"},
        {"13033684303", "Duanjingyu", "Shanghai Pudong"},
        {"13045678901", "Lizongxi", "Taiyuan Xiaodian"},
        {"13600135864", "Changzhikun", "Shanxi Yuncheng Yongji"},
        {"13600135864", "Li Qi", "Hangzhou Xihu"},
        {"13600134000", "Sun Ba", "Nanjing Gulou"},
        {"13300133000", "Liuyiping", "Shanxi Taiyuan Yingze"},
        {"13934202204", "Zhaihaosen", "Wuhan Jianghan"},
        {"13100131000", "Panwenbo", "Shanxi Taiyuan Jiancaoping"},
        {"13000130000", "Wang Wei", "Chongqing Dadukou"},
        {"13912345678", "Liu Bei", "Chengdu Wuhou"},
        {"15811112222", "Guan Yu", "Luoyang Xigong"},
        {"13700001111", "Zhang Fei", "Langzhong Gucheng"},
        {"15222223333", "Zhao Yun", "Zhengzhou Guancheng"},
        {"15233334444", "Huang Zhong", "Nanyang Wolong"},
        {"15200000000", "Lijie", "Shanxi taiyuan xiaodian"},
        {"19999999999", "Zzz Zzz", "Shanghai lujiazui"},
        {"15211111111", "Single Word", "Short Addr"},
        {"12121212121", "llllllllll          ", "Beijing Changping Changping Road No.100"},
        //外国人
        {"13144445555", "O'Conner", "Dublin Ireland"},
        {"13255556666", "André", "Paris France"},
        {"13366667777", "Kim Lee", "Seoul Gangnam"},
        {"13477778888", "Van Der Waals", "Amsterdam Centrum"}
    };

    // 初始化散列表
    for (const auto& rec : initialRecords) {
        allRecords.push_back(rec);
        phoneHash.insert(rec, rec.phoneNumber);
        nameHash.insert(rec, rec.userName);
    }

    // 主菜单循环
    int choice;
    while (true) {
        printHeader("电话号码查询系统");
        cout << "           1. 添加新记录" << endl;
        cout << "           2. 按电话号码查询" << endl;
        cout << "           3. 按用户名查询" << endl;
        cout << "           4. 显示所有记录" << endl;
        cout << "           5. 散列表统计信息" << endl;
        cout << "           6. 模糊查询" << endl;
        cout << "           7. 编辑记录" << endl;  
        cout << "           8. 退出系统" << endl;
        cout << "\033[1;33m" << setw(30) << "请输入操作选项(1-7) :" << " \033[0m";

        if (!(cin >> choice)) {
            cout << "\033[1;31m输入无效，请重新输入！\033[0m" << endl;
            clearInputBuffer();
            continue;
        }
        clearInputBuffer();

        switch (choice) {
        case 1: { // 添加新记录
            PhoneRecord newRecord;
            printHeader("添加新记录");

            // 电话号码输入验证
            while (true) {
                cout << "请输入电话号码 (11位数字): ";
                getline(cin, newRecord.phoneNumber);

                if (!CheckPhoneNum(newRecord.phoneNumber)) {
                    cout << "\033[1;31m格式错误：必须为11位数字！\033[0m" << endl;
                }
                else if (phoneHash.contains(newRecord.phoneNumber)) {
                    cout << "\033[1;31m该电话号码已存在！\033[0m" << endl;
                }
                else {
                    break;
                }
            }

            // 用户名输入验证
            while (true) {
                cout << "请输入用户名 (仅含字母和空格): ";
                getline(cin, newRecord.userName);

                if (!CheckUserName(newRecord.userName)) {
                    cout << "\033[1;31m格式错误：仅允许字母和空格！\033[0m" << endl;
                }
                else if (nameHash.contains(newRecord.userName)) {
                    cout << "\033[1;31m该用户名已存在！\033[0m" << endl;
                }
                else {
                    break;
                }
            }

            // 地址输入
            cout << "请输入地址: ";
            getline(cin, newRecord.address);

            // 添加到系统
            allRecords.push_back(newRecord);
            phoneHash.insert(newRecord, newRecord.phoneNumber);
            nameHash.insert(newRecord, newRecord.userName);

            cout << "\n\033[1;32m✓ 记录添加成功！\033[0m" << endl;
            break;
        }

        case 2: { // 按电话号码查询
            string phone;
            printHeader("按电话号码查询");
            cout << "请输入电话号码: ";
            getline(cin, phone);

            PhoneRecord* result = phoneHash.search(phone);
            if (result) {
                printHeader("查询结果");
                printRecordHeader();
                printRecord(*result);
                cout << string(60, '-') << endl;
            }
            else {
                cout << "\n\033[1;31m 未找到匹配的记录！\033[0m" << endl;
            }
            break;
        }

        case 3: { // 按用户名查询
            string name;
            printHeader("按用户名查询");
            cout << "请输入用户名: ";
            getline(cin, name);

            PhoneRecord* result = nameHash.search(name);
            if (result) {
                printHeader("查询结果");
                printRecordHeader();
                printRecord(*result);
                cout << string(60, '-') << endl;
            }
            else {
                cout << "\n\033[1;31m 未找到匹配的记录！\033[0m" << endl;
            }
            break;
        }

        case 4: { // 显示所有记录
            printHeader("电话簿记录 (" + to_string(allRecords.size()) + "条)");
            printRecordHeader();

            for (const auto& rec : allRecords) {
                printRecord(rec);
            }
            cout << string(60, '-') << endl;
            break;
        }

        case 5: { // 散列表统计信息
            printHeader("散列表统计");
            cout << "\n===== 电话号码散列表 =====" << endl;
            phoneHash.printStats();

            cout << "\n===== 用户名散列表 =====" << endl;
            nameHash.printStats();
            break;
        }

        case 6: { // 模糊查询
            string keyword;
            printHeader("模糊查询");
            cout << "请输入查询关键字: ";
            getline(cin, keyword);

            // 移除首尾空格
            keyword.erase(0, keyword.find_first_not_of(" "));
            keyword.erase(keyword.find_last_not_of(" ") + 1);

            if (keyword.empty()) {
                cout << "\033[1;33m 查询关键字不能为空！\033[0m" << endl;
                break;
            }

            fuzzySearch(allRecords, keyword);
            break;
        }

        case 7: { // 编辑记录
            editRecord(phoneHash, nameHash, allRecords);
            break;
        }



        case 8: // 退出系统
            printHeader("系统退出");
            cout << "\033[1;32m感谢使用电话查询系统！再见！\033[0m" << endl;
            return 0;

        default:
            cout << "\033[1;31m无效选择，请重新输入！\033[0m" << endl;
        }
    }

    return 0;
}